/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/19
 */
//简单的邮递计划
//    四条东西方向的街道
//    交区最西北角的那个路口有一个邮局
//    哈密顿回路?_?
public class P5_2_1435 {

    static HashMap<Long, BigInteger> routeMap = new HashMap<>();

    public static void main(String[] argv) {
        System.out.println(getRoute(9));
    }

    public static BigInteger getRoute(long n) {
        if (n == 1) {
            return new BigInteger("0");
        } else if (n == 2) {
            return new BigInteger("2");
        } else if (n == 3) {
            return new BigInteger("4");
        } else if (n == 4) {
            return new BigInteger("12");
        } else {
            if (routeMap.containsKey(n)) {
                return routeMap.get(n);
            }
            //BigInteger number = getRoute(n - 4) - getRoute(n - 3) * 2
            // + getRoute(n - 2) * 2 + getRoute(n - 1) * 2;
            BigInteger number = getRoute(n - 4)
                    .subtract(getRoute(n - 3).multiply(new BigInteger("2")))
                    .add(getRoute(n - 2).multiply(new BigInteger("2")))
                    .add(getRoute(n - 1).multiply(new BigInteger("2")));
            routeMap.put(n, number);
            return number;
        }
    }
}
